package SlidingWindow.Medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC0438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        if (p.length() > s.length()) return ret;
        // p一定不比s长

        if (s.isEmpty()) return ret;

        // 计算p的直方图
        char[] sArray = s.toCharArray(), pArray = p.toCharArray();
        int[] hist = new int[26], stdHist = new int[26];
        for (char c : pArray) {
            stdHist[c - 'a']++;
        }

        int left = 0, right = 0;
        int subStrLength = 0;
        while (right < s.length()) {
            subStrLength++;
            hist[sArray[right] - 'a']++;
            if (subStrLength >= p.length()) { // 子串到达p的长度，进行检查
                if (Arrays.equals(hist, stdHist)) {
                    ret.add(left);
                    hist[sArray[left] - 'a']--;
                    subStrLength--;
                    left++;
                }
                else { // 直方图不一致，子串中的某个字符数量比p更多
                    char targetChar;
                    for (targetChar = 'a'; targetChar <= 'z'; targetChar++) {
                        if (hist[targetChar - 'a'] > stdHist[targetChar - 'a']) break;
                    }

                    while (sArray[left] != targetChar) {
                        hist[sArray[left] - 'a']--;
                        left++;
                        subStrLength--;
                    }
                    // 此时left一定指向多出来的字符
                    hist[sArray[left] - 'a']--;
                    left++;
                    subStrLength--;
                }
            }
            right++; // right始终指向待考察的字符
        }

        return ret;
    }
}
